/**
 * @file 435.Non-overlappingIntervals.cc
 * @author snow-tyan (zziywang@163.com)
 * @brief {Life is too short to learn cpp.}
 * @version 0.1
 * @date 2021-11-28
 * 
 * @copyright Copyright (c) 2021
 * 
 * 区间问题
 * 435.无重叠区间
 * 452.用最少数量的箭射爆气球
 * 56.合并区间
 */

#include <cassert>

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

template <typename T>
void print(const T &Containers)
{
    typename T::const_iterator it = Containers.begin();
    cout << '[';
    while (it != Containers.end()) {
        cout << *it << ", ";
        ++it;
    }
    cout << ']';
    cout << endl;
}

class Solution
{
public:
    // 435. 无重叠区间
    // 求删几个区间后所有区间无重叠
    static bool compareEndLess(vector<int> &a, vector<int> &b)
    {
        assert(a.size() == 2);
        assert(b.size() == 2);
        return a[1] < b[1];
    }
    int eraseOverlapIntervals(vector<vector<int>> &intervals)
    {
        // 按end升序排序所得只有两种情况：画图理解
        // 1 start < start_next < end 重叠
        // 2 end < start_next  无重叠
        // 按右端点排序可以保证：区间左边不会有其他区间
        // 如何保证这样得到的是最优？ 局部最优->总体最优
        int cnt = 0; // 计数重叠区间
        int n = intervals.size();
        std::sort(intervals.begin(), intervals.end(), compareEndLess);
        int end = intervals[0][1];
        for (int i = 1; i < n; ++i) {
            if (intervals[i][0] < end) {
                ++cnt;
            } else {
                end = intervals[i][1]; // 只有发现不重叠区间才更新end
            }
        }
        return cnt;
    }
    // 452. 用最少数量箭射爆气球
    // 重叠区间可以一箭射爆
    int findMinArrowShots(vector<vector<int>> &points)
    {
        // 排序只是移动纵坐标
        if (points.empty()) {
            return 0;
        }
        int cnt = 1;
        int n = points.size();
        std::sort(points.begin(), points.end(), compareEndLess);
        int end = points[0][1];
        for (int i = 1; i < n; ++i) {
            // 擦边也算一箭
            if (points[i][0] > end) {
                ++cnt;
                end = points[i][1];
            }
        }
        return cnt;
    }
    // 56.合并所有重叠区间
    vector<vector<int>> merge(vector<vector<int>> &intervals)
    {
        // start升序 end降序
        // 相邻区间只有三种情况：全覆盖、错位相交（可合并）、不重叠
        int n = intervals.size();
        std::sort(intervals.begin(), intervals.end(),
                  [](const vector<int> &a, const vector<int> &b) {
                      if (a[0] == b[0]) {
                          return a[1] > b[1];
                      }
                      return a[0] < b[0];
                  });
        int start = intervals[0][0], end = intervals[0][1];
        vector<vector<int>> res;
        res.emplace_back(intervals[0]);
        for (int i = 1; i < n; ++i) {
            if (intervals[i][1] < end) { // 覆盖
                continue;
            } else if (intervals[i][0] <= end) { // 相交
                res.pop_back();
                res.emplace_back(start, intervals[i][1]);
                intervals[i][0] = start; // 更新前端点
            } else if (intervals[i][0] > end) { // 不重叠
                res.emplace_back(intervals[i]);
            }
            start = intervals[i][0];
            end = intervals[i][1];
        }
        return res;
    }
};

void test435()
{
    vector<vector<int>> nums1 = {{1, 2}, {2, 3}, {3, 4}, {1, 3}};
    vector<vector<int>> nums2 = {{1, 2}, {1, 2}, {1, 2}};
    vector<vector<int>> nums3 = {{1, 2}, {2, 3}};
    cout << Solution().eraseOverlapIntervals(nums1) << endl;
    cout << Solution().eraseOverlapIntervals(nums2) << endl;
    cout << Solution().eraseOverlapIntervals(nums3) << endl;
}

int main()
{
    test435();
    return 0;
}